This invention relates to the field of traffic engineering, and in particular to the creation and maintenance of explicit routes for virtual circuits, such as Label-Switched Paths (LSPs), subject to routing and other network traffic constraints.
Traffic engineering generally includes the tasks of predicting the behavior of communications networks, and modifying the behavior as required to provide an efficient and effective use of resources throughout the network. Traffic Engineering includes the process of creating ‘virtual circuits’ between source and destination nodes in order to make efficient use of network resources, to satisfy routing constraints for the circuits, and to improve network survivability. In the field of Multi-Protocol Label Switching, for example, traffic engineering includes determining primary and secondary routes for Label Switched Paths (LSPs).
A variety of tools and techniques have been developed to identify optimal, or near-optimal, configurations of modeled networks. In the field of label switching network configurations, tools are available to align the requirements placed on defined communication paths (LSPs) between nodes of the network with the resources available in an existing or proposed network, and thereby identify near-optimal routes for these virtual circuits.
As networks become more and more complex, with dynamic changes occurring regularly, the actual optimization of a network's performance becomes a daunting and sometimes infeasible or impractical task. When a change or addition to a network is implemented, the truly-optimal use of this changed or added resource may require a change to dozens, or hundreds, of other network resources. In like manner, when a change or addition to the communication requirements or constraints is made, the truly-optimal solution may also require many changes to the network. Often, due to the risks of introducing unanticipated problems with each change, and the well recognized maxim of “if it isn't broken, don't ‘fix’ it”, few, if any, of the ancillary changes are actually implemented. Because of these factors, and others, most real-world networks gradually become substantially different from their ideally optimized configuration.
Conventional optimization tools and techniques receive a model of the network, including the capabilities of each link, and a list of required circuits between nodes and their associated constraints. The conventional tools then apply one or more allocation schemes to determine a preferred route for each circuit so as to satisfy each of the constraints subject to the network capabilities. Unfortunately, the resultant preferred or optimal solution often has little correspondence to the current configuration of the network, and the number of changes required to implement the proposed solution makes such an implementation infeasible or impractical.
When a change is proposed to a network, such as the addition of a new virtual circuit, the conventional traffic engineering tools are used to facilitate identification of a configuration that satisfies the requirements for this new circuit, but these tools conventionally provide this ‘incremental’ solution by assuming that all previously defined circuits are locked, and the new routes for the new circuit must be found based on the currently available unsubscribed link capabilities. Alternatively, all previously defined circuits are not constrained to be locked, and a global optimization is performed. However, as noted above, such a global solution in a large network often requires an inordinate number of changes, and is rarely practical to implement.
Hybrid solutions are commonly used, wherein all explicitly routed circuits are constrained to be locked, but dynamically routed circuits, such as Constrained Shortest Path First (CSPF) routed circuits, are not constrained. In such a solution, the identified routes associated with the new circuit are explicitly added to the existing set of explicit routes, while all of the remaining changes associated with the dynamically routed circuits are ignored. Although these ignored changes are deemed irrelevant, because the originally routed circuits were unknown to begin with, the accumulation of sub-optimal solutions often leads to performance deficiencies that are difficult to isolate and correct.
If a solution for the new circuit cannot be found, the network manager may be required to manually delete previously explicitly routed circuits, in the hope of freeing-up subscriptions on links of the new circuit. However, most managers would consider such a hit-and-miss approach only as a last resort, and only if the new circuit has sufficient priority to warrant risking the introduction of problems on the deleted circuits, which had been working fine.
It would be advantageous to be able to identify a minimal number of changes required to provide a traffic engineering optimized solution to implement a proposed change to a network. It would be advantageous to be able to identify optimized performance-improvement changes to a network that do not, per se, require a substantial number of individual changes relative to the current configuration of the network. It would be advantageous to identify the possible performance-improvement changes that provide the best performance improvement per implemented change. It would be advantageous to be able to identify the degree of performance improvement achievable as a function of the total number of changes required to achieve each degree of performance improvement.
These advantages, and others, can be realized by a system and method that assesses an existing network configuration and identifies the potential changes to the existing configuration that provide the greatest incremental improvements to the performance of the network. In a preferred embodiment, the user of the system identifies the maximum number (N) of changes that may be implemented in an existing network, and the system provides a set of possible reconfigurations, each requiring fewer than N changes. Of particular note, the ‘best’ changes are defined without constraining all circuits to be locked, or all circuits to be unlocked. Existing circuits are ‘preferably locked’, but, unless otherwise indicated, can be changed if the change provides a definitive improvement. The objective function may include conventional load-balancing objectives, or other objectives, such as a global minimization of circuit route lengths. In the realm of label switching protocols, the existing network configuration may include a combination of explicitly routed label-switched paths, as well as those routed based on conventional dynamic inline routing protocols such as CSPF, OSPF, IS-IS, and so on. In a preferred embodiment, a graph of performance improvement(s) v. the number of changes is provided, so that the impact of implementing each set of changes can be visualized.
In a preferred embodiment of this invention, existing routes in the current configuration of the network for primary and/or secondary explicit routes are used, as are the existing routes for the circuits that are dynamically routed by Label-Switched Routers (LSRs), or other virtual circuit creation tools, rather than being explicitly routed. For example, Constrained Shortest Path First (CSPF) routes can be imported from the current operational network. Each circuit is tagged to identify the extent to which the circuit's current routes can be changed, and a limit to the total number of circuits whose routes may be changed during the incremental route optimization can be imposed.
This incremental traffic engineering optimization is particularly effective for applying additional constraints (delay constraints, subscription constraints, etc.) to an existing configuration and determining the minimal number of changes necessary to put the current configuration in compliance with these constraints. It is also particularly effective for adding new circuits to the configuration and determining the minimum number of re-routes necessary to support the new circuits, and for making topology changes (new links, link bandwidth changes, traffic engineering bandwidth and class type changes) and identifying a preferred set of circuits that should be re-routed based on these changes.
This invention also facilitates the task of incrementally migrating from dynamically routed network configuration to an explicitly routed configuration by identifying a subset of circuits whose re-routing will most improve the network performance.
This invention also facilitates improved network reliability by allowing network managers to plan for service interruption by identifying the set of circuits that are routed over a given network resource (node, link or shared-risk group) and generating a set of re-routed circuits with routes that avoid the resource. In like manner, secondary explicit routes for a circuit can be generated that are disjoint with respect to resources used in the existing primary explicit routes.
As noted above, this invention facilitates effective and efficient traffic engineering by re-optimizing a traffic engineering solution by identifying the circuits whose re-routing will most effectively improve the total network quality and/or performance, subject to existing and/or new constraints, including a limit on the number of permitted changes.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.